﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Qiang.QMath
{
    public class KdNode
    {


        public KdNode(KdPoint key, object value)
        {
            this.key = key;
            this.value = value;

            this.left = null;
            this.right = null;
            this._isDeleted = false;
         }


        internal readonly KdPoint key;  //节点坐标

        internal object value; //节点值

        internal KdNode left;  //此节点的左节点

        internal KdNode right;  //此节点的右节

        private bool _isDeleted;  //表示此节点是否有效，是否已经删除了


        public bool IsDeleted
        {
            get { return _isDeleted; }
            set { _isDeleted = value; }
        }


        /// <summary>
        /// 插入一个新节点，其实这应该是属于kdTree的功能，只是要实现只能在这里实现
        /// </summary>
        /// <param name="key">要插入节点的坐标</param>
        /// <param name="value">要插入节点的值</param>
        /// <param name="node">在哪个位置进行插入</param>
        /// <param name="lev">表示当前第几维</param>
        /// <param name="k">维度，坐标一共有几维 </param>
        /// <returns></returns>
        public static KdNode Insert(KdPoint key,object value,KdNode currentNode,int lev,int k)
        {
            if (currentNode == null)  //如果当前节点为空，则实例当前节点
            {
                currentNode = new KdNode(key, value);
            }
            else if (key.Equals(currentNode.key)) //如果当前节点与要插入的坐标相同，则赋值，并且设置当前节点为有效节点
            {
                if (currentNode.IsDeleted) //如果此结点无效，设为有效并重新赋值
                {
                    currentNode.IsDeleted = false;
                    currentNode.value = value;
                }
                else  //如果当胆节点有效，则冲突了，要报错
                { 
                    //插入不进去，因为与现有节点坐标冲突了
                }
            }
            else //最后就是判断是要在当胆节点的左侧还是右侧插入
            {
                if (key[lev] > currentNode.key[lev])
                {
                    //如果新插入节点的坐标的 lev维度 的值 大于当前节点的lev维度的值，则在当前节点的右侧进行插入，否则在左侧进行插入
                    Insert(key, value, currentNode.right, (lev + 1) % k, k);
                }
                else
                {
                    Insert(key, value, currentNode.left, (lev + 1) % k, k);
                }
            }

            return currentNode;
        
        }


        /// <summary>
        /// 查找特定节点
        /// </summary>
        /// <param name="key">要查找的节点的坐标</param>
        /// <param name="currentNode">当前节点（判断这个节点是否是要查找的，如果不是则判断是向它的右节点走还是左节点走）</param>
        /// <param name="k">节点坐标的维度</param>
        /// <returns></returns>
        public static KdNode Search(KdPoint key, KdNode currentNode, int k)
        {
            //从维度0开始判断，判断要查找的节点与当前节点此维度下坐标值的大小以判断是向当前节点的右节点还是左节点走
            //结束标志为当前节点为要查找节点或当前节点为空
            //循环标志为维度的变化，% k表示当前维度不超过总维度
            for (int lev = 0; currentNode != null; lev = (lev + 1) % k)
            {
                if (currentNode.IsDeleted == false && key.Equals(currentNode.key))
                {
                    return currentNode;
                }
                //判断走左节点还是右节点
                currentNode = currentNode.key[lev] < key[lev] ? currentNode.right : currentNode.left;
            }

            return null;
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="currentNode">当前节点</param>
        /// <param name="target">目标点</param>
        /// <param name="rect"></param>
        /// <param name="maxDisance"></param>
        /// <param name="lev">表示当前第几维</param>
        /// <param name="k">维度</param>
        /// <param name="neighbors">存储结果</param>
        public static void Nearest(KdNode currentNode, KdPoint target,KdRect rect,
            double maxDisance,int lev,int k,KdNeighbors neighbors)
        {

            if (currentNode == null) return;

            int s = lev % k;  //保证当前维度不能大于总维度了

            KdPoint currentPoint = currentNode.key;

            double currentPtToTarget = KdPoint.SquareDistance(currentPoint, target); //当前节点到目标点的距离


            KdRect leftRect = rect;
            KdRect rightRect = rect.Copy();

            leftRect.Max[s] = currentPoint[s];
            rightRect.Min[s] = currentPoint[s];





        }






    }
}
